// This is unpublished source code. Michah Lerner 2006

package trieMatch.keywordMatcher;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.Map.Entry;

import trieMatch.Interfaces.Aggregator;
import trieMatch.Interfaces.MapFactory;
import trieMatch.Interfaces.Matcher;
import trieMatch.Interfaces.Similarity;
import trieMatch.keywordMatcher.KeyMatch.MatchType;
import trieMatch.util.aggregation.AggregatorBase;
import trieMatch.util.coll.Pair;

/**
 * Matcher implementation of lexicographical tries with score-based aggregation over the URL of each (partial) match.
 * Multiple results of an URL are reduced down to one result, and the scores of each contributing match are aggregated
 * into the total score the the URL. <br>
 * <br>
 * <b>NOTE</b>
 * <li> A URL is specified by <i>at least</i> one keymatch
 * <li> A StructuredElement specifies <i>at least</i> one URL
 * 
 * <br>
 * <br>
 * The completeness of a match depends on the kmType. See {@link http://www.google.com.by/enterprise/gsa/features.html}
 * for documentation on Keymatch for detail.<br>
 * <br>
 * All <i>complete</i> matches are reduced and aggregated.<br>
 * <br>
 * 
 * 
 * @author Michah.Lerner
 * 
 */

public class TrieMatcher implements Matcher {
	final Sequencer sq = new Sequencer();
	static final List<KMDefinition> emptyMatchable = new ArrayList<KMDefinition>(0);
	static final Collection<Pair<String, Integer>> emptyReduction = new ArrayList<Pair<String, Integer>>(1);
	static public Aggregator aggregator;
	Tiers tierHead; // Reentrant for multiple non-synchronized readers
	Stack<Integer> depthStack;
	StructuredElement lookingFor;

	enum SequenceType {
		sameInorder, sameNotInorder, different
	}

	public TrieMatcher() {
		this(null);
	}

	public TrieMatcher(final Tiers tiers) {
		this(tiers, new Sequencer());
	}

	public TrieMatcher(final Tiers tiers, final Sequencer sequencer) {
		this.tierHead = tiers;
		this.depthStack = new Stack<Integer>();
	}

	public MapFactory mapFactory() {
		class mapFactory implements MapFactory {
			public Map<String, Tiers> newMap() {
				return new HashMap<String, Tiers>();
			}
		}
		return new mapFactory();
	}

	public Similarity similarity = new ResultScorer_prefixPhrase(); // new ResultScorer_cos();//

	public float sim(final StructuredElement element, final String description) {
		return similarity.sim(element, description);
	}

	public float sim(final StructuredElement element, final StructuredElement description) {
		return similarity.sim(element, description);
	}

	public static void setAggregator(final String aggregatorName, final String aggregatorParm) {
		aggregator = AggregatorBase.getAggregator(aggregatorName, aggregatorParm);
	}

	public List<KMDefinition> findMatch(final String s) {
		return findMatch(sq, s);
	}

	public List<KMDefinition> findMatch(final Sequencer sq, final String s) {
		if (s == null || s.length() == 0) { return emptyMatchable; }
		return findMatch(sq.arrange(s));
	}

	public List<KMDefinition> findMatch(final StructuredElement lookingFor) {
		this.lookingFor = lookingFor;
		return findMaxMatch(tierHead, 0);
	}

	List<KMDefinition> findMoreMaxMatch(final Tiers tier, final int pos) {
		depthStack.push(pos);
		final List<KMDefinition> res = findMaxMatch(tier, pos + 1);
		depthStack.pop();
		return res;
	}

	List<KMDefinition> findMaxMatch(final Tiers current, final int pos) {
		if (pos >= lookingFor.size()) { return current.instances != null
				? validForMatchtype(current.instances)
				: emptyMatchable; }

		final Tiers nTier = current.successors.get(lookingFor.get(pos).getValue());
		if (nTier != null) {
			depthStack.push(pos);// INLINED: final List<KMDefinition> v1 = findMoreMaxMatch(nTier, pos);
			final List<KMDefinition> v1 = findMaxMatch(nTier, pos + 1);
			depthStack.pop();

			final List<KMDefinition> v2 = findMaxMatch(current, pos + 1);
			if (v1.size() < v2.size()) {
				v2.addAll(v1);
				return v2;
			} else {
				v1.addAll(v2);
				return v1;
			}
		}
		return findMaxMatch(current, pos + 1);
	}

	/**
	 * Check for identically ordered contentIndex sets, between the matched input and the phrasematch or exactmatch
	 * text. This optimization is equivalent to a more expensive value comparison, as the input is known to contain all
	 * the indexedTerms of the match text.
	 * 
	 */
	private boolean sameSequence(final KMDefinition km) {
		if (km.element.size() != depthStack.size()) { return false; }
		final int sdiff = km.element.getIndex(0) - lookingFor.getIndex(depthStack.get(0));
		for (int depth = 1; depth < Math.min(km.element.size(), depthStack.size()); depth++) {
			if (km.element.getIndex(depth) - lookingFor.getIndex(depthStack.get(depth)) != sdiff) { return false; }
		}
		return true;
	}

	/*******************************************************************************************************************
	 * Dereference the index array to check if result violated the subsequence constraint.
	 * 
	 * @param km
	 *            containing permutation order, i.e. for input "big can art" [2 0 1]
	 * @return
	 */
	boolean inSequence(final KMDefinition km) {
		final Integer[] sequenceVerifier = new Integer[lookingFor.size() + 1];
		for (int depth = 0; depth < Math.min(km.element.size(), depthStack.size()); depth++) {
			sequenceVerifier[lookingFor.getIndex(depthStack.get(depth))] = km.element.getIndex(depth);
		}
		Integer prior = 0;
		for (final Integer x : sequenceVerifier) {
			if (x == null) {
				continue;
			} else if (x < prior) {
				return false;
			} else {
				prior = x;
			}
		}
		return true;
	}

	void showStacks(final KMDefinition km) {
		System.out.println("insequence=" + inSequence(km));
		System.out.println("-----siz=" + km.element.size());
		for (int depth = 0; depth < Math.min(km.element.size(), depthStack.size()); depth++) {
			final int kmL = km.element.getIndex(depth);
			final String kmString = km.element.getValue(depth);
			final int dp = depthStack.get(depth);
			final int looking = lookingFor.getIndex(dp);
			final String itemString = lookingFor.getValue(dp);
			System.out.printf("%03d  %03d  %03d  %03d | %10s %10s%n", depth, kmL, dp, looking, kmString, itemString);
		}
	}

	/**
	 * validForMatchtype implements keymatch semantic
	 * 
	 * @param kmDef
	 * @return List of valid keymatches
	 */

	protected List<KMDefinition> validForMatchtype(final List<KMDefinition> kmDef) {
		final List<KMDefinition> valueResult = new ArrayList<KMDefinition>();
		for (final KMDefinition km : kmDef) {
			if ((km.kType == MatchType.KEYWORDMATCH) || (km.kType == MatchType.INORDERMATCH && inSequence(km))
					|| (km.kType == MatchType.PHRASEMATCH && sameSequence(km))
					|| (km.kType == MatchType.EXACTMATCH && depthStack.size() == lookingFor.size() && sameSequence(km))) {
				valueResult.add(km);
			}
		}
		return valueResult;
	}

	/**
	 * reduce aggregates scores according to implementation of RecordTally. <b>NOTE:</b> With overide functions, this
	 * can use a similarity function that compares the users' input with the attributes of the keymatch. In one case it
	 * uses the description, in the other it uses the keywords. Neither one does explicit stopword removal. The
	 * invocation of the resultScorer.sim takes either a string or a structuredElement. The string form handles the raw
	 * description stored in kmDef.description. The structuredElement form handles the keywords
	 * 
	 * @param list
	 * @return List unique keymatches, ordered by aggregated score
	 */
	@SuppressWarnings("static-access")
	public Collection<Pair<String, Integer>> reduce(final List<KMDefinition> list) {
		if (list == null || list.size() == 0) { return emptyReduction; }
		return (new RecordTally(list)).sortEntries();
	}

	public Collection<KMDefinition> kmReducer(final List<KMDefinition> list) {
		final Collection<Pair<String, Integer>> reduced = reduce(list);
		final Map<String, KMDefinition> reverseMap = new HashMap<String, KMDefinition>();
		final Collection<KMDefinition> result = new ArrayList<KMDefinition>();
		for (final KMDefinition kmd : list) {
			if (reverseMap.get(kmd.url) == null) {
				reverseMap.put(kmd.url, new KMDefinition(kmd));
			}
		}
		for (final Pair<String, Integer> p : reduced) {
			final KMDefinition km = reverseMap.get(p.s());
			km.score = p.t();
			result.add(km);
		}
		return result;
	}

	/**
	 * Implement the business logic for aggregation and ranking of results.
	 * 
	 * @author Michah.Lerner
	 * 
	 */
	private class RecordTally {
		Map<String, Integer> smap;

		RecordTally() {
			smap = new HashMap<String, Integer>();
		}

		RecordTally(final List<KMDefinition> kmd) {
			this();
			for (final KMDefinition kmDef : kmd) {
				addItem(kmDef.url, kmDef.score);
			}
		}

		// Compute argmax( P(h|D) ) as p(D|h)p(h)
		void addItem(final String key, final int tally) {
			final Integer i = smap.get(key);
			if (i == null) {
				smap.put(key, tally);
			} else {
				smap.put(key, aggregator.aggregate(i, tally));
			}
		}

		Collection<Pair<String, Integer>> sortEntries() {
			final List<Pair<String, Integer>> sts = new ArrayList<Pair<String, Integer>>();
			for (final Entry<String, Integer> me : smap.entrySet()) {
				sts.add(new Pair<String, Integer>(me.getKey(), me.getValue()));
			}
			Collections.sort(sts, (new CompareEntries()));
			return sts;
		}

		class CompareEntries implements Comparator<Pair<String, Integer>> {
			public int compare(final Pair<String, Integer> o1, final Pair<String, Integer> o2) {
				if (o1.t().equals(o2.t())) { return o1.s().compareTo(o2.s()); }
				return o2.t().compareTo(o1.t());
			}
		}
	}
}
